Residue Number Systems by P. V. Ananda Mohan

Author:P. V. Ananda Mohan
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

(7.1)

Similarly for second redundant modulus also A 2(X) is determined. If these two are equal, there is no error. This technique is called overflow consistency check.

An example will be illustrative. Consider the moduli set {5, 6, 7, 11} where 5 and 6 are actual moduli and 7, 11 are the redundant moduli . For a legitimate number, 17 = (2, 5, 3, 6), we have A 1(X) considering the moduli set {5, 6, 7} as 0 and A 2(X) considering the moduli set {5, 6, 11} as zero. On the other hand, consider that an error has occurred in the residue corresponding to the modulus 5 to change the residues as (3, 5, 3, 6). It can be verified that A 1(X) = 3 and A 2(X) = 9 showing the inconsistency. The authors suggest adding to A i (X) where N is the number of moduli (not considering redundant moduli ) to take care of the possible negative values of A i (X).

Watson and Hastings [2] error correction procedure uses base extension to redundant moduli . The difference between the original and reconstructed redundant residues Δ1, Δ2 is used to correct the errors. If Δ1 = 0 and Δ2 = 0, then no error has occurred. If one of them is non-zero, the old residue corresponding to this redundant modulus is replaced by new one. If both are non-zero, then they are used to address a correction table of entries.

Yau and Liu [6] modified this procedure and suggest additional computations in stead of using look-up tables. Considering a n moduli set with r additional redundant moduli , they compute the sets . Here the residues are determined by base extension assuming the RNS contains all moduli except those within the set. If the first set has zero entries, there is no error. If exactly one of these is non-zero, corresponding redundant residue is in error. If more than one element is non-zero, then an iterative procedure checks the remaining sets to identify the incorrect residue in a similar manner. This means that the information residue is in error.

Barsi and Maestrini [5] and Mandelbaum [3] suggest the concept of product codes, where each residue is multiplied by a generator A which is larger than the moduli and mutually prime to all moduli. Thus, of the available dynamic range MA, only M values represent the original RNS.

Given a positive integer A, called the generator of the code, an integer X in the range [0, M] is a legitimate number in the product code of the generator A if X = 0 mod A and A is mutually prime to all m i . Any X in the range [0, M] such that X ≠ 0mod A is said to be an illegitimate number. The advantage of this technique is that when addition of X 1 and X 2 is performed, if overflow has occurred , it can be found by checking whether where X S  = (X 1 + X 2) mod M. Then, we need to check whether the number is legitimate. If , an additive overflow has been detected.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.